/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package practice.v2;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:InsertSort.java v1.0 2018/8/15 上午10:23 LvJing Exp $
 */
public class InsertSort {

    /**
     * 直接插入排序：属于插入排序，第一趟保证前两个数有序，即第一个数比比较的数小（第二个数），不管，比它大，就把第一个数插到第二个数的位置；
     * 第二趟保证前三个数有序。。。
     */
    public void insertSort(int[] arr) {
        if (arr == null || arr.length == 0 || arr.length == 1)
            return;

        // 从第二个数开始比较，保证排序
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1] > temp; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    @Test
    public void test01() {
        Random random = new Random();
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++)
            arr[i] = random.nextInt(100);
        System.out.println(Arrays.toString(arr));
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
